As an increasing number of applications and services are being made available over networks such as the Internet, an increasing number of content, application, and/or service providers are turning to technologies such as cloud computing. Cloud computing, in general, is an approach to providing access to electronic resources through services, such as Web services, where the hardware and/or software used to support those services is dynamically scalable to meet the needs of the services at any given time. A customer typically will rent, lease, or otherwise pay for access to resources through the cloud, such that the customer does not have to purchase and maintain the hardware and/or software to provide access to these resources. A potential disadvantage to such an approach, at least from a customer point of view, is that the resources typically are at a location under control of the provider of those resources, and thus are out of the direct control of the customer. In order to help ensure that resources allocated to the customer perform tasks only under direction of that customer, the provider environment can support request authentication to prevent unauthorized parties from accessing the resources. Customers would like some assurance that the service provider will honor only requests from the customer and will reject any requests that might have been tampered with or otherwise falsely generated.